package specialArray;

import java.io.LineNumberReader;
import java.util.Arrays;

public class Solution {
    public int specialArray(int[] nums) {
        // 思路 计数+前缀和
        int max = Arrays.stream(nums).max().getAsInt();
        int[] prevSum = new int[max+1]; // 前缀和数组
        int[] arr = new int[max+1]; // 计数数组
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++; // 统计数组中每个元素出现的次数
        }
        prevSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prevSum[i] = arr[i]+prevSum[i-1];
        }
        for (int x = 1; x < max; x++) {
            if(prevSum[max]-prevSum[x-1]==x){
                return x;
            }
        }
        return -1;

//        Arrays.sort(nums);
//        int n = nums.length;
//        for (int x = 1; x < nums.length; x++) {
//            // 恰好有x个元素>=x ==== nums[n-x]>=x&&nums[n-x-1]<x
//            if(nums[n-x]>=x&&nums[n-x-1]<x){
//                return x;
//            }
//        }
//        return -1;
    }
}
